\section{雇用问题}

\begin{enumerate}[label=\textbf{\thesection{}-\arabic*}]
  \item \textbf{证明: 假设在程序HIRE-ASSISTANT的第4行中，我们总是能够决定哪一个应聘者最佳，这就蕴含我们知道应聘者排名的总次序。}

        \textbf{Show that the assumption that we are \emph{always able to} (一定可以) determine which candidate is best in line 4 of procedure HIRE-ASSISTANT implies that we know a \emph{total order} (排序) on the ranks of the candidates.}

        \textbf{必要性}：如果我们有所有应聘者能力的排名，那么显然可以知道当前的应聘者们中谁是最好的。
 
        \textbf{充分性}：如果我们始终能从当前的应聘者们找到最好的，有了这个操作，就可以对应聘者进行排序(选择排序)，排序后得到应聘者能力排名。

  \item \textbf{描述RANDOM($a$, $b$)过程的一种实现，它只调用RANDOM(0, 1)。作为$a$和$b$的函数，你的程序的期望运行时间是多少？}
        
        算法描述如下：
\begin{alltt}
RANDOM(\(a\), \(b\))
    \(num\gets{}0\)
    for \(i\gets0\) to \(\lceil{}log\sb{2}(b-a)\rceil\)
        do \(val\gets{}num | \)(RANDOM(\(0\), \(1\))\(\:\ll{}i\))
            if \(val+a\leqslant{}b\)
               then \(num\gets{}val\)
               else return RANDOM(\(a\), \(b\))  \(\triangleright\) Try again
    return \(a+num\)
\end{alltt}        
        上述算法调用$\lceil log_2(b-a)\rceil + 1$次RANDOM(0, 1)。
        第$i$次RANDOM(0, 1)的结果构成$num$的二进制第$i$位。
        若结果大于$b$，则重新算。
        
        时间复杂度为$O(\lceil log_2(b-a)\rceil + 1)$。
        
        错误算法：
\begin{alltt}
RANDOM(\(a\), \(b\))
    \(num\gets{}a\)
    for \(i\gets1\) to \(b-a\)
        do \(num\gets{}num + \)RANDOM(\(0\), \(1\))
    return \(num\)
\end{alltt}
        %运行时间为$O(b - a)$。
        以上算法调用$b-a$次RANDOM(0, 1)并求和，这样得出的结果服从二项分布，而不是均匀分布。

  \item \textbf{假设你希望以各$1/2$的概率输出0和1。你可以自由使用一个输出0或1的过程BIASED-RANDOM。它以概率$p$输出1，以概率$1 - p$输出0，其中$0 < p < 1$，但是你并不知道$p$的值。给出一个利用BIASED-RANDOM作为子程序的算法，返回一个无偏向的结果，即以概率$1/2$返回0，以概率$1/2$返回1。作为$p$的函数，你的算法的期望运行时间是多少？}

        算法描述如下：
\begin{alltt}
UNBIASED-RANDOM
    while TRUE
        do \(x\gets \)BIASED-RANDOM
           \(y\gets \)BIASED-RANDOM
           if \(x\ne{}y\)
               then return \(x\)
\end{alltt}
        上述算法只可能返回0和1两种值，其中返回0的概率为$\text{Pr}\{x = 0\ \text{and}\ y = 1\} = (1 - p)p$，返回1的概率为$\text{Pr}\{x = 1\ \text{and}\ y = 0\} = p(1 - p)$。因此返回0或1的概率是相等的。

        算法的每一次迭代都相当于是一次Bernoulli trial，成功的概率为$2p(1 - p)$。算法的运行时间取决于迭代次数，即Bernoulli trial取得一次成功所要进行的试验次数。这一系列试验的概率分布满足geometric distribution，分布的期望即是迭代次数。根据(C.31)公式得出期望为$1/(2p(1 - p))$，因此算法的期望运行时间为$O(1/(2p(1 - p)))$。

        {\kaishu 算法参考资料: Instructor's Manual}
\end{enumerate}

\section{指示器随机变量}

\begin{enumerate}[label=\textbf{\thesection{}-\arabic*}]
  \item \textbf{在HIRE-ASSISTANT中，假设应聘者以随机的顺序出现，正好雇用一次的概率是多少？正好雇用$n$次的概率又是多少？}
  
        Instructor's Manual:
	  
        Since HIRE-ASSISTANT always hires candidate 1, it hires exactly once if and only if no candidates other than candidate 1 are hired. This event occurs when candidate 1 is the best candidate of the $n$, which occurs with probability $1/n$.
        
        HIRE-ASSISTANT hires n times if each candidate is better than all those who were interviewed (and hired) before. This event occurs precisely when the list of ranks given to the algorithm is $\langle{}1, 2, \dots, n\rangle$, which occurs with probability $1/n!$.
        
        正好雇佣一次事件A：第一个面试者为能力最强的人，后面$n-1$个人随意排列(反正也不会被录用)。
\begin{align}
  \text{Pr}\{A\} &= \frac{(n-1)!}{n!} \nonumber \\
                 &= \frac{1}{n} 
\end{align}       
        正好雇用$n$次事件B：面试者按照能力由弱到强顺序登场，这个排列出现概率为：
\begin{align}
  \text{Pr}\{B\} &= \frac{1}{n!}
\end{align}  
        
        %根据HIRE-ASSISTANT算法，第一个应聘者是肯定会被雇用的，因此正好雇用一次的概率就是第一个应聘者之后的所有人都比他差的概率，即$1/n$。

        %雇用$n$次也就是每一个应聘者都会被雇用，根据(5.4)，概率为$1/n!$。

  \item \textbf{在HIRE-ASSISTANT中，假设应聘者以随机的顺序出现，正好雇用两次的概率是多少？}

        第一个应聘者是肯定会被雇用的，但不可以是所有应聘者中最强的那个，因为这样就导致只能雇用一次，因此第一个应聘者的rank值只能是$[1, n - 1]$。当第一个应聘者取得区间中的任意一个值时，$n$个应聘者都有可能等于那个值，概率为$1/n$。

        当第一个应聘者被雇用后，下一个被雇用的肯定是rank值为$n$的人。但在雇用这个最强的人（以下简称Superman）之前不能把第一个应聘者淘汰了，这就得要求所有比第一个应聘者rank值高的人都必须在Superman之后面试。假设第一个应聘者的rank值为$i$，于是就有$n - i$个应聘者比他的rank值高，而Superman必须是这$n - i$个应聘者中第一个被面试的人，这个事件发生的概率是$1/(n - i)$，设这个事件用$F$表示。

        设$E_i$代表第一个应聘者的rank值为$i$的事件，$A$代表正好雇用两次这个事件，因此：
\begin{align}
  \text{Pr}\{A\} &= \text{Pr}\{F \cap (E_1 \cup E_2 \cup \cdots \cup E_{n-1})\} \nonumber \\
                 &= \text{Pr}\{(F \cap E_1) \cup (F \cap E_2) \cup \cdots \cup (F \cap E_{n-1})\} \nonumber \\
                 &= \sum_{i=1}^{n-1} \text{Pr}\{F \cap E_i\} \nonumber \\
                 &= \sum_{i=1}^{n-1} \left(\frac{1}{n - 1} \cdot \frac{1}{n}\right) \nonumber \\
                 &= \frac{1}{n} \cdot H_{n-1}
\end{align}
        其中$H_{n-1}$代表第$n - 1$个调和级数。

  \item \textbf{利用指示器随机变量来计算掷$n$次骰子总和的期望值。}        
        
  \item \textbf{利用指示器随机变量来解帽子保管问题（hat-check problem）: 有$n$位顾客，他们每个人给餐厅负责保管帽子的服务生一顶帽子。服务生以随机的顺序将帽子归还给顾客。请问拿到自己帽子的客户的期望数目是多少？}

        令指示器随机变量$X_i$对应于第$i$个顾客拿到自己帽子的事件，随机变量$X$表示$n$位顾客中拿到自己帽子的人数，则
\begin{align}
  \text{E}[X] &= \text{E}\left[\sum_{i=1}^{n} X_i\right] \nonumber \\
              &= \sum_{i=1}^{n} \text{E}[X_i] \nonumber \\
              &= \sum_{i=1}^{n} \frac{1}{n} \nonumber \\
              &= 1
\end{align}
        因此拿到自己帽子的客户的期望数目是1。

  \item \textbf{假设$A[1\texttt{..}n]$是由$n$个不同的数构成的数组。如果$i < j$且$A[i] > A[j]$，则称$(i, j)$对为$A$的逆序对（inversion）。（思考题2-4中有更多关于逆序对的例子。）假设$A$的元素形成$<1, 2, \cdots, n>$上的一个均匀随机排列。利用指示器随机变量来计算$A$中逆序对的期望数目。}

        令指示器随机变量$X_k$对应于第$k$个$(i, j)$对是逆序对的事件，随机变量$X$表示$A$中逆序对的数目，其中$\text{E}[X_k] = 1/2$，则
\begin{align}
  \text{E}[X] &= \text{E}\left[\sum_{k=1}^{\binom{n}{2}} X_k\right] \nonumber \\
              &= \sum_{k=1}^{\binom{n}{2}} \text{E}[X_k] \nonumber \\
              &= \sum_{k=1}^{\binom{n}{2}} \frac{1}{2} \nonumber \\
              &= \binom{n}{2} \frac{1}{2} \nonumber \\
              &= \frac{n(n - 1)}{4}
\end{align}
        因此$A$中逆序对的期望数目为$n(n - 1)/4$。
\end{enumerate}

\section{随机算法}

\begin{enumerate}[label=\textbf{\thesection{}-\arabic*}]
  \item \textbf{Marceau教授对引理5.5证明过程中使用的循环不变式表示异议。他对在第1次迭代之前循环不变式是否为真理提出质疑。他的理由是人们可以容易地宣称空数组不包含0排列。因此空数组包含0排列的概率应该是0，所以在第1次迭代之前循环不变式无效。请改写过程RANDOMIZE-IN-PLACE，使其相关的循环不变式在第1次迭代之前对非空数组仍适用，并未你的过程修改引理5.5的证明。}

        修改后的算法为：
\begin{alltt}
RANDOMIZE-IN-PLACE(\(A\))
    \(n\gets{}length[A]\)
    swap \(A[1]\leftrightarrow{}A[\text{RANDOM(}1\text{, }n\text{)}]\)
    for \(i\gets{}2\) to \(n\)
        do swap \(A[i]\leftrightarrow{}A[\text{RANDOM(}i\text{, }n\text{)}]\)
\end{alltt}
        这样在第一次循环迭代之前，子数组$A[1\texttt{..}1]$包含一个1排列的概率为$(n - i + 1)!/n! = 1/n$。

  \item \textbf{Kelp教授决定写一个过程来随机产生非同一排列（identity permutation）的任意排列。他提出了如下的过程:}

\begin{alltt}
PERMUTE-WITHOUT-IDENTITY(\(A\))
    \(n\gets{}length[A]\)
    for \(i\gets{}1\) to \(n-1\)
        do swap \(A[i]\leftrightarrow{}A[\text{RANDOM(}i+1\text{, }n\text{)}]\)
\end{alltt}

        \textbf{这段代码实现了Kelp教授的意图了吗？}

        答案是没有实现。虽然上面这个算法不会产生与原排列一模一样的随机排列，但同时也造成了其它一些排列无法产生。比如序列为$<1, 2, 3>$，上面这个算法是绝对不会得到$<1, 3, 2>$这种排列的。

  \item \textbf{假设不是将元素$A[i]$与子数组$A[i\text{..}n]$中的随机一个元素相交换，而是将它与数组任何位置上的随机元素相交换:}

\begin{alltt}
PERMUTE-WITH-ALL(\(A\))
    \(n\gets{}length[A]\)
    for \(i\gets{}1\) to \(n\)
        do swap \(A[i]\leftrightarrow{}A[\text{RANDOM(}1\text{, }n\text{)}]\)
\end{alltt}

        \textbf{这段代码会产生均匀随机排列吗？为什么会？或为什么不会？}

        不会产生均匀随机排列。还是以序列$<1, 2, 3>$为例，这个序列一共有$3! = 6$种排列，而PERMUTE-WITH-ALL算法可以产生$3^3 = 27$种情况，也就是说这27种情况有很多是重复的，而每一种排列的重复次数必须是$27/6$才行，显然这个除法得到的结果不可能是整数，因此PERMUTE-WITH-ALL是错误的。

  \item \textbf{Armstrong教授建议使用下列过程来产生均匀随机排列:}

\begin{alltt}
PERMUTE-BY-CYCLIC(\(A\))
    \(n\gets{}length[A]\)
    \(offset\gets\text{RANDOM(}1\text{, }n\text{)}\)
    for \(i\gets{}1\) to \(n\)
        do \(dest\gets{}i+offset\)
           if \(dest>n\)
               then \(dest\gets{}dest-n\)
           \(B[dest]\gets{}A[i]\)
    return \(B\)
\end{alltt}

        \textbf{证明任意元素$A[i]$出现在$B$中任何特定位置的概率都是$1/n$。然后通过证明其结果不是均匀随机排列来表明Armstrong教授错了。}

        一旦$offset$确定，随机排列也就确定，而$offset$取得任何一个值的概率为$1/n$，因此任意元素$A[i]$出现在$B$中任何特定位置的概率都是$1/n$。

        由于$offset$只有$n$种取值，导致最终产生的随机排列也最多只有$n$种，这显然是不正确的，因为一共有$n!$种。

  \item \textbf{证明程序PERMUTE-BY-SORTING的数组$P$中，所有元素都唯一的概率至少为$1 - 1/n$。}

  \item \textbf{解释如何实现算法PERMUTE-BY-SORTING，来处理两个或更多优先级相同的情况。亦即，即使有两个或更多的优先级相同，你的算法也必须产生一个均匀随机排列。}
\end{enumerate}

\section{概率分析和指示器随机变量的进一步使用}

\begin{enumerate}[label=\textbf{\thesection{}-\arabic*}]
  \item \textbf{一个房间里必须要有多少人，才能让某人和你生日相同的概率至少为1/2？必须要有多少人，才能让至少两个人生日为7月4日的概率大于1/2？}

  \item \textbf{假设将球投入到$b$个盒子里。每一次投掷都是独立的，并且每个球落入任何盒子的机会都相等。在至少有一个盒子包含两个球之前，期望的投球次数是多少？}

  \item \textbf{在生日悖论的分析中，要求各生日彼此独立这一点是否是很重要的？或者，是不是只要每两个人的生日互相独立就足够了？证明你的答案。}

  \item \textbf{一个聚会需要邀请多少人，才能让其中很可能有3个人的生日相同？}

  \item \textbf{在大小为$n$的集合中，一个$k$串实际上是一个$k$排列的概率是多少？这个问题和生日悖论有什么关系？}

  \item \textbf{假设将$n$个球投入$n$个盒子里，每次投球都是独立的，并且每个球落入任何盒子的机会都相等。空盒子的期望数量是多少？正好有一个球的盒子的期望数量又是多少？}

  \item \textbf{为使序列长度的下界变得更加准确，请证明在$n$次均匀硬币的抛掷中，不出现比$\text{lg}n - 2\text{lg}\text{lg}n$更长的连续正面序列的概率小于$1/n$。}
\end{enumerate}

\section*{思考题}
\addcontentsline{toc}{section}{思考题}

\begin{enumerate}[label=\textbf{\thechapter{}-\arabic*}]
  \item \textbf{概率计数}

        {\kaishu 利用一个$b$位的计数器，一般只能计数到$2^b - 1$，而用R. Morris的概率计数法，则可以计到一个大得多的值，但代价是精度有所损失。}

        {\kaishu 对$i = 0, 1, \dots, 2^b - 1$，令计数器的值$i$表示计数$n_i$，且各$n_i$构成了一个非负的递增数列。假设计数器的初值为0，代表计数$n_0 = 0$。作用于计数器上的INCREMENT操作以概率的方式包含值$i$。如果$i = 2^b - 1$，则报告溢出错误。否则，计数器以概率$1/(n_{i+1} - n_i)$增加1，以概率$1 - 1/(n_{i+1} - n_i)$保持不变。}

        {\kaishu 对于所有的$i \geqslant 0$，如果选择$n_i = i$，则此计数器就是一个平常的计数器。如果选择$n_i = 2^{i-1}$（$i > 0$），或$n_i = F_i$（第$i$个斐波那契数，见3.2节），则会出现一些有趣的情况。}

        {\kaishu 对这个问题，假设$n_{2^b - 1}$已足够大，从而使得发生溢出错误的概率可以忽略。}

        \begin{enumerate}[label=\alph*)]
          \item {\kaishu 证明在执行了$n$次INCREMENT操作之后，计数器所表示的数的期望值正好是$n$。}

          \item {\kaishu 对有计数器所表示的计数的方差的分析要依赖于$n_i$的序列。让我们来看一下简单情况: 对所有$i \geqslant 0$，$n_i = 100i$。在执行了$n$次INCREMENT操作之后，估计计数器所表示的数的方差。}
        \end{enumerate}

        \begin{enumerate}[label=\alph*)]
          \item 设$X_j$表示在第$j$次执行INCREMENT操作之后计数器增加的值，$S_n$表示执行$n$次INCREMENT操作之后计数器表示的数。

                因此$S_n = X_1 + X_2 + \cdots + X_j$，$j = 1, 2, \dots, n$，$\text{E}[S_n] = \sum_{j=1}^{n} \text{E}[X_j]$。而根据期望的定义
\begin{align}
  \text{E}[X_j] &= \left((n_{j+1} - n_j) \cdot \frac{1}{n_{j+1} - n_j}\right) + \left(0 \cdot \left(1 - \frac{1}{n_{j+1} - n_j}\right)\right) \nonumber \\
         &= 1
\end{align}
                因此$\text{E}[S_n] = n$。

          \item 定义随机变量$X_j$与$S_n$，含义同上。因为$X_j$都是两两独立的变量，根据公式(C.28)，$\text{Var}[S_n] = \sum_{j=1}^{n} \text{Var}[X_j]$。

                $n_{i+1} - n_i = 100(i + 1) - 100i = 100$，根据公式(C.26)
\begin{align}
  \text{Var}[X_j] &= \text{E}[X_j^2] - \text{E}^2[X_j] \nonumber \\
                  &= \left(\left(100^2 \cdot \frac{1}{100}\right) + \left(0 \cdot \frac{99}{100}\right)\right) - 1^2 \nonumber \\
                  &= 99
\end{align}
                因此$\text{Var}[S_n] = 99n$。
        \end{enumerate}
\end{enumerate}